/*
 * @lc app=leetcode.cn id=92 lang=java
 *
 * [92] 反转链表 II
 *
 * https://leetcode-cn.com/problems/reverse-linked-list-ii/description/
 *
 * algorithms
 * Medium (48.27%)
 * Likes:    265
 * Dislikes: 0
 * Total Accepted:    28.4K
 * Total Submissions: 58.9K
 * Testcase Example:  '[1,2,3,4,5]\n2\n4'
 *
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 *
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NULL
 *
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(m == n)  return head;
        ListNode start = head, end = head, prev = null, nt = null;
        while(--m > 0) {
            prev = start;
            start = start.next;
        }
        while(--n > 0) {
            end = end.next;
        }

        ListNode p = end.next, cur = start, next = cur.next;
        while(cur != end ) {
            cur.next = p;
            p = cur;
            cur = next;
            if(cur != null)
                next = cur.next;
        }
        cur.next = p;
        if(prev != null) {
            prev.next = cur;
        }
        return prev == null ? cur : head;

    }
}
// @lc code=end

